package com.chj.linkedlist;

public class Code04_ReverseList {

	public static class Node {
		public int val;
		public Node next;

		public Node(int data) {
			this.val = data;
		}
	}

	public static Node reverseList(Node head) {
		Node pre = head;
		Node next = head.next;
		head.next = null;

		Node ans = reverseNode(pre, next);
		return ans;
	}

	public static Node reverseNode(Node pre, Node right) {
		Node temp = null;
		while (right != null) {
			temp = right.next;
			right.next = pre;
			pre = right;
			right = temp;
		}

		return pre;
	}

	public static DoubleNode reverseDoubleList(DoubleNode head) {

		DoubleNode pre = head;
		DoubleNode next = head.next;
		head.next = null;
		head.last = next;
		DoubleNode ans = reverseDoubleNode(pre, next);
		return ans;
	}

//	DoubleNode pre = null;
//	DoubleNode next = null;
//	while (head != null) {
//		next = head.next;
//		head.next = pre;
//		head.last = next;
//		pre = head;
//		head = next;
//	}
//	return pre;
	public static DoubleNode reverseDoubleNode(DoubleNode pre, DoubleNode next) {
		DoubleNode temp = null;
		while (next != null) {
			temp = next.next;
			next.next = pre;
			next.last = temp;
			pre = next;
			next = temp;
		}

		return pre;
	}

	public static class DoubleNode {
		public int val;
		public DoubleNode next;
		public DoubleNode last;

		public DoubleNode(int val) {
			this.val = val;
		}
	}

	public static void printLinkedList(Node head) {
		System.out.print("Linked List: ");
		while (head != null) {
			System.out.print(head.val + " ");
			head = head.next;
		}
		System.out.println();
	}

	public static void printDoubleLinkedList(DoubleNode head) {
		System.out.print("Double Linked List: ");
		DoubleNode end = null;
		while (head != null) {
			System.out.print(head.val + " ");
			end = head;
			head = head.next;
		}
		System.out.print("| ");
		while (end != null) {
			System.out.print(end.val + " ");
			end = end.last;
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Node head1 = new Node(1);
		head1.next = new Node(2);
		head1.next.next = new Node(3);
		head1.next.next.next = new Node(4);
		head1.next.next.next.next = new Node(5);
		printLinkedList(head1);
		head1 = reverseList(head1);
		printLinkedList(head1);

		DoubleNode head2 = new DoubleNode(1);
		head2.next = new DoubleNode(2);
		head2.next.last = head2;
		head2.next.next = new DoubleNode(3);
		head2.next.next.last = head2.next;
		head2.next.next.next = new DoubleNode(4);
		head2.next.next.next.last = head2.next.next;
		head2.next.next.next.next = new DoubleNode(5);
		head2.next.next.next.next.last = head2.next.next.next;
		printDoubleLinkedList(head2);
		printDoubleLinkedList(reverseDoubleList(head2));

	}
}
